import java.util.*;

public class Test {

     public class TreeNode {
     int val = 0;
     TreeNode left = null;
     TreeNode right = null;

     public TreeNode(int val) {
     this.val = val;

     }
    }
    public class Solution {
        //返回的第一个指针，即为最小值，先定为null
        public TreeNode head = null;
        //中序遍历当前值的上一位，初值为最小值，先定为null
        public TreeNode prev = null;
        public TreeNode Convert(TreeNode pRootOfTree) {
            if(pRootOfTree == null) {
                //中序递归，叶子为空则返回
                return null;
            }
            //首先递归到最左最小值
            Convert(pRootOfTree.left);
            //找到最小值，初始化head与pre
            if(prev == null) {
                head = pRootOfTree;
                prev = pRootOfTree;
            }
            //当前节点与上一节点建立连接，将pre设置为当前值
            else {
                prev.right = pRootOfTree;
                pRootOfTree.left = prev;
                prev = pRootOfTree;
            }
            Convert(pRootOfTree.right);
            return head;
        }
    }
}
